package main

import (
	"fmt"
	"math/rand"
	"time"
)

// 大顶堆
var maxHeapItems = make([]int, 0)

// 堆长度
var maxHeapCount = 0

func insert(n int) {
	maxHeapItems = append(maxHeapItems, n)
	maxHeapCount++
	maxHeapFixUp()
}

// 上浮
func maxHeapFixUp() {
	var targetNum = maxHeapCount - 1
	for {
		if targetNum <= 0 {
			break
		}
		var parentIndex = (targetNum - 1) / 2
		if maxHeapItems[targetNum] < maxHeapItems[parentIndex] {
			break
		}
		maxHeapItems[targetNum], maxHeapItems[parentIndex] = maxHeapItems[parentIndex], maxHeapItems[targetNum]
		targetNum = parentIndex
	}
}

// 取出元素 取出元素后 将最后一个元素放在根元素上
// 元素下沉 将元素移动到它合适的地方
func sellOrderFixDown() {
	rootIndex := 0
	length := maxHeapCount
	for {
		leftChildIndex := 2*rootIndex + 1
		rightChildIndex := 2*rootIndex + 2

		// 孩子节点中较大的节点
		maxChildIndex := leftChildIndex
		// 防止越界
		if leftChildIndex >= length {
			// 至少存在左孩子
			break
		}

		if rightChildIndex < length {
			// 存在 右孩子
			if maxHeapItems[rightChildIndex] > maxHeapItems[leftChildIndex] {
				maxChildIndex = rightChildIndex
			}
		}
		// 根元素 > 孩子节点较大者
		if maxHeapItems[rootIndex] >= maxHeapItems[maxChildIndex] {
			break
		}
		maxHeapItems[rootIndex], maxHeapItems[maxChildIndex] = maxHeapItems[maxChildIndex], maxHeapItems[rootIndex]
		rootIndex = maxChildIndex
	}
}

// 取出元素
func maxHeapPoll() int {
	if maxHeapCount <= 0 {
		return -1
	}
	root := maxHeapItems[0]
	maxHeapItems[0] = maxHeapItems[maxHeapCount-1]
	maxHeapCount--
	sellOrderFixDown()
	return root
}

func main() {

	rand.Seed(time.Now().Unix())

	for i := 0; i < 10; i++ {
		num := rand.Intn(50)
		insert(num)
		fmt.Println(num)
	}
	fmt.Println(">>>>>>>>")

	for i := 0; i < 10; i++ {
		fmt.Println(maxHeapPoll())
	}
}
